#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
//void SeletSort(HeapType* arr, int n) {
//	int max, min;
//	int begin = 0;
//	int end = n - 1;
//	max = min = 0;
//	while (begin<end) {
//		
//		for (int i = begin+1; i <= end; i++) {
//			max = min = begin;
//			if (arr[i] <arr[min]) {
//				min = i;
//			}
//			if (arr[i]>arr[max]) {
//				max = i;
//			}
//		}
//		if (max == begin) {
//			max = min;
//		}
//		Swap(&arr[begin], &arr[min]);
//		Swap(&arr[end], &arr[max]);
//		end--;
//		begin++;
//		
//	}
//
//}
void SeletSort(int* arr, int n) {
	int end = n - 1;
	int begin = 0;
	int max, min;
	max = min = 0;
	while (begin < end) {
		max = min = begin;
		for (int i = begin + 1; i <= end; i++)
		{
		
			if (arr[i] > arr[max]) {
				max = i;

			}
			if (arr[i] < arr[min])
			{
				min = i;
			}

		}
		if (max == begin) {
			max = min;
		}
		Swap(&arr[min], &arr[begin]);
		Swap(&arr[max], &arr[end]);
		begin++;
		end--;

	}

}
void Inite(Heap* p) {
	p->a = NULL;
	p->capacity = p->size = 0;



}
void Push(Heap* php, HeapType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HeapType* tmp = (HeapType*)realloc(php->a, newcapacity * sizeof(HeapType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}
void Pop(Heap* p) {
	Swap(&p->a[0], &p->a[p->size - 1]);



	p->size--;
	AdjustDown(p->a, 0, p->size);


}
bool Empty(Heap* p) {
	return p->size == 0;


}
HeapType Top(Heap* p) {

	return p->a[0];

}
void Print(Heap* p) {
	{
		while (!Empty(p))
		{
			printf("%d ", Top(p));
			Pop(p);
		}

	}
}
void Swap(HeapType* a, HeapType* b) {

  	int tem = *a;
	*a = *b;
	*b = tem;

}
void AdjustUp(HeapType* a, int child) {

		
		int parent = (child - 1) / 2;
		while (child > 0) {
			if (a[child] < a[parent])
			{
				Swap(&a[child], &a[parent]);
				child = parent;
				parent = (child - 1) / 2;

			}

			else
			{
				break;
			}

		}

	}


	
void AdjustDown(HeapType* a, int parent, int n) {
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1]) {
			child = child + 1;


		}
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}

	}

}
void HeapSort1(HeapType* arr, int n) {
	for (int i = 0; i < n; i++) {
		AdjustUp(arr, i);

	}

}
void HeapSort2(HeapType* arr, int n) {

	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {


		AdjustDown(arr, i, n);

}
	int end = n - 1;
	for (int i = end; i > 0; i--) {
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;



	}
}